/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 12
 * Time: 9:50
 */
//力扣148 排序链表
class ListNode {
     int val;
   ListNode next;
    ListNode() {}
   ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
class Solution {
    public ListNode sortList(ListNode head) {
        return sortListF(head, null);//第二个参数传的是null
    }
    private ListNode sortListF(ListNode head, ListNode end) {
        if(head == null) return null;
        if(head.next == end)
        { 
            head.next = null;//把各个节点断开
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while((fast != end) && (fast.next != end)) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode mid = slow;
        ListNode list1 = sortListF(head, mid);//要用list1和list2接收返回值，list1和list2是两个有序链表的头节点
        ListNode list2 = sortListF(mid, end);//因为要把各个节点断开，所以分开右边时要写mid而不是写mid.next
        return merge(list1, list2);//合并两个有序链表，参数要传两个有序链表的头节点，最后返回合并结束后的总头节点
    }
    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode node = new ListNode();
        ListNode th = node;
        while ((head1 != null) && (head2 != null)) {
            if(head1.val > head2.val) {
                th.next = head2;
                th = th.next;
                head2 = head2.next;
            }else {
                th.next = head1;
                th = th.next;
                head1 = head1.next;
            }
        }
        if(head1 != null) {
            th.next = head1;
        }
        if(head2 != null) {
            th.next = head2;
        }
        return node.next;
    }
}